package top100;

/**
 * @author Godc
 * @description
 */
public class DetectCycle {
    public static void main(String[] args) {
        reverseBetweenSolution s = new reverseBetweenSolution();
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(5);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        s.reverseBetween(listNode,2,4);
    }
}
class DetectCycleSolution {
    public ListNode detectCycle(ListNode head) {
        if(head==null) return null;
        ListNode slow = head,fast = head;
        while(true){
            if(fast==null||fast.next==null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow) break;
        }
        fast = head;
        while(slow!=fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class reverseBetweenSolution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head==null) return null;
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre,end;
        pre = dummy;
        end = dummy;
        int cnt = 1;
        while(cnt<left){
            pre = pre.next;
            cnt++;
        }
        ListNode start = pre.next;
        end = pre;
        while(cnt<=right+1){
            end = end.next;
            cnt++;
        }
        ListNode next = end.next;
        end.next = null;
        pre.next = reverse(start);
        start.next = next;
        return dummy.next;
    }
    public ListNode reverse(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode cur = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
}
